/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-03-28
 * Time: 22:29
 */


class Solution {

    //含冷冻期
    public int maxProfit1(int[] prices) {
        int n = prices.length;
        //1.创建dp表
        //dp[i][0]第i天结束后处于买出状态
        //dp[i][1]第i天结束后处可交易状态
        //dp[i][2]第i天结束后处于冷冻期状态
        int[][] dp = new int[n][3];
        //2.初始化
        dp[0][0] = -prices[0];dp[0][1] = dp[0][2] = 0;
        //3.填表顺序
        //4.状态转移
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]);
            dp[i][2] = dp[i-1][0]+prices[i];
        }
        //5.返回值
        return Math.max(dp[n-1][1],dp[n-1][2]);
    }

    //含手续费
    public int maxProfit2(int[] prices, int fee) {
        int n = prices.length;
        //1.创建dp表
        //dp[i][0]
        //dp[i][1]
        int[][] dp = new int[n][2];
        //2.初始化
        dp[0][0] = -prices[0]; dp[0][1] = 0;
        //3.状态转移
        //4.填表顺序 同时 从左往右
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][1]-prices[i],dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i]-fee,dp[i-1][1]);
        }
        //5.返回结果
        return dp[n-1][1];
    }

    //买卖股票最佳时期I
    public int maxProfit3(int[] prices) {
        //条件 只能买卖一次股票且不能在同一天
        int n = prices.length;
        //1.创建dp表
        //dp[i][0]表示第i天结束股票是买入状态最大利润
        //dp[i][1]表示第i天结束股票是卖出状态最大利润
        int[][] dp = new int[n][2];
        //2.边界判断
        if(n == 1 || n == 0) {
            return 0;
        }
        //3.初始化
        dp[0][0] = -prices[0]; dp[0][1] = 0;
        //4.状态转移
        //5.填表顺序 左到右
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        //6.返回结果
        return dp[n-1][1];
    }

    //买卖股票最佳时期II
    //条件 可以买卖多次
    public int maxProfit4(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];dp[0][1] = 0;
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }
    //买卖股票最佳时期III
    //条件最多完成两笔交易
    public int maxProfit5(int[] prices) {
        int n = prices.length;
        //1.创建dp表
        //两个状态
        //f[i][j] 表示第i天交易j笔结束后处于买入状态最大利润
        //g[i][j] 表示第i天交易j笔结束后处于卖出状态最大利润
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        //2.初始化
        f[0][0] = -prices[0];g[0][0] = 0;
        for(int j = 1; j <= 2; j++) {
            f[0][j] = Integer.MIN_VALUE / 2;
            g[0][j] = Integer.MIN_VALUE / 2;
        }
        //3.状态转移
        //4.填表顺序
        for(int i = 1; i < n;i++) {
            for(int j = 0 ; j < 3; j++) {
                f[i][j] = Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j] = g[i-1][j];
                if(j-1 >= 0) {
                    g[i][j] = Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
                }
            }
        }
        //5.返回值
        int ret = g[n-1][0];
        for(int j = 0; j < 3; j++) {
            ret = Math.max(ret,g[n-1][j]);
        }
        return ret;
    }

    public int maxProfit6(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][5];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for(int i = 1; i < n;i++) {
            dp[i][0] = dp[i-1][0];
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        return dp[n-1][4];
    }

    //买卖股票最佳时期IV
    //最多完成k次交易
    public int maxProfit7(int k,int[] prices) {
        int n = prices.length;
        //1.创建dp表
        //两个状态
        //f[i][j] 表示第i天交易j笔结束后处于买入状态最大利润
        //g[i][j] 表示第i天交易j笔结束后处于卖出状态最大利润
        int[][] f = new int[n][k+1];
        int[][] g = new int[n][k+1];
        //2.初始化
        f[0][0] = -prices[0];g[0][0] = 0;
        for(int j = 1; j <= k; j++) {
            f[0][j] = Integer.MIN_VALUE / 2;
            g[0][j] = Integer.MIN_VALUE / 2;
        }
        //3.状态转移
        //4.填表顺序
        for(int i = 1; i < n;i++) {
            for(int j = 0 ; j < k+1; j++) {
                f[i][j] = Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j] = g[i-1][j];
                if(j-1 >= 0) {
                    g[i][j] = Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
                }
            }
        }
        //5.返回值
        int ret = g[n-1][0];
        for(int j = 0; j < k+1; j++) {
            ret = Math.max(ret,g[n-1][j]);
        }
        return ret;
    }
}
